Computer technology is continually advancing, resulting in a continuing stream of computers that are more powerful than their predecessors. One such area of advancement, and one that is of great importance to many designers as well as end users, is that of computer graphics. Computer graphics are used in a wide variety of fields, including entertainment (e.g., games), computer aided design, system modeling, and so forth.
Typically, computers manage graphics by manipulating small uniform geographic shapes that often times are triangles. Graphical objects and surfaces are described using groups of these triangles, and the triangles themselves are typically organized as a collection of vertices (i.e., each triangle is represented by a set of three vertices). Such a representation for triangles is well suited to hardware-accelerated rendering. However, such a representation also makes determining triangle and vertex adjacency cumbersome and computationally expensive. For example, given a particular vertex it can be very time-consuming to determine what its edge sharing neighbor vertices are. Determining triangle and vertex adjacency is crucial to many algorithms that deal with surfaces (e.g., refinement and smoothing algorithms, simplification and level of detail algorithms, etc.), yet the current systems for representing triangles are not well-suited to determining such triangle and vertex adjacency.
The invention described below addresses these disadvantages, providing improved structures and processes to manage triangles.